#include<iostream>
using namespace std;
#include<queue>
#include<vector>
#include<unordered_map>
class Solution {
public:
    class cmp {
    public:
        bool operator()(pair<int, int>& a1, pair<int, int>& a2) {
            return a1.second < a2.second;
        }
    };
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> ma;
        for (auto& e : arr)
            ++ma[e];
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
        int sum = 0;
        for (auto& e : ma) {
            sum += e.second;
            que.push(e);
        }
        int now = 0, ans = 0;
        while (!que.empty()) {
            ++ans;
            now += que.top().second;
            que.pop();
            if (now >= sum / 2)
                break;
        }
        return ans;
    }
};